#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;


//300.最长递增子序列
int lengthOfLIS(vector<int>& nums){
    int n = nums.size();

    //状态表示 dp[i]表示以i位置元素为结尾的所有子序列中，增长的递增子序列长度
    //初始化，单独的一个元素就是一个子序列，长度为，所以状态表中初始值全部设置为1
    vector<int> dp(n, 1);

    //填表
    for (int i = 1; i < n; i++){
        for (int j = i - 1; j >= 0; j--){
            if(nums[i]>nums[j]){
                //状态转移方程
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    //返回值 遍历整个状态表，找到以某个位置元素为结尾时，最长的递增子序列长度
    int ret = 0;
    for(auto x : dp){
        ret = max(ret, x);
    }
    return ret;
}

//376.摆动序列
int wiggleMaxLength(vector<int>& nums){
    int n = nums.size();

    //状态表示 
    //f[i]表示以i位置元素为结尾的所有子序列中，最后一个是上升趋势的最长摆动序列
    //g[i]表示以i位置元素为结尾的所有子序列中，最后一个是下降趋势的最长摆动序列
    //初始化，单独的一个元素就是一个摆动序列，长度为1，所以状态表中初始值全部设置为1
    vector<int> f(n, 1);
    vector<int> g(n, 1);

    //填表
    for (int i = 1; i < n; i++){
        for (int j = i - 1; j >= 0; j--){
            //状态转移方程
            if(nums[j]>nums[i]){
                g[i] = max(g[i], f[j] + 1);
            }
            else if(nums[j]<nums[i]){
                f[i] = max(f[i], g[j] + 1);
            }
        }
    }

    //返回值 遍历两个状态表，找到以某个位置为结尾时的最长摆动序列
    int ret = 0;
    for (int i = 0; i < n; i++){
        ret = max(max(f[i], g[i]), ret);
    }
    return ret;
}


//673.最长递增子序列
int findNumberOfLIS(vector<int>& nums){
    int n = nums.size();

    //状态表示
    //len[i]表示以i位置元素为结尾的所有子序列中，最长的递增子序列的长度
    //count[i]表示以i位置元素为结尾的所有子序列中，最长的递增子序列的个数
    //初始化时，单独的一个元素就是一个子序列，长度为1
    vector<int> len(n, 1);
    vector<int> count(n, 1);

    //填表
    for (int i = 1; i < n; i++){
        for (int j = i - 1; j >= 0; j--){
            if (nums[j] < nums[i]){
                //状态转移方程+贪心策略（边找以“i元素为结尾”最长的递增子序列，边统计个数）
                if (len[i] == len[j] + 1){
                    count[i] += count[j];
                }
                else if (len[i] < len[j] + 1){
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                }
            }
        }
    }

    //返回值 贪心策略统计最长递增子序列的个数
    int maxlen = len[0], ret = count[0];
    for (int i = 1; i < n; i++){
        if (maxlen == len[i]){
            ret += count[i];
        }
        else if (maxlen < len[i]){
            maxlen = len[i];
            ret = count[i];
        }
    }
    return ret;
}


//646.最长数对链
int findLongestChain(vector<vector<int>>& pairs){
    //预处理 先按照从小到大排序 [a,b] [c,d] c>a 由d>c可以得到，d>a
    sort(pairs.begin(), pairs.end());
    int n = pairs.size();

    //状态表示 dp[i]表示以i位置的数对为结尾的所有数对链中最长的数对链长度
    vector<int> dp(n, 1);

    //填表
    for (int i = 1; i < n; i++){
        for (int j = i - 1; j >= 0; j--){
            //状态转移方程
            if (pairs[i][0] > pairs[j][1]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    //返回值 找到以某个位置的数对为结尾时最长的数对链长度
    int ret = 0;
    for(auto x : dp){
        ret = max(ret, x);
    }
    return ret;
}

//1218.最长定差子序列
int longestSubsequence(vector<int>& arr, int difference){
    //创建一个哈希表用来存放元素和对应状态值
    unordered_map<int, int> hash;
    int n = arr.size();

    //状态表示 dp[i]表示以i位置元素为结尾的所有子序列中，最长的定差子序列长度
    vector<int> dp(n, 1);
    hash[arr[0]] = 1;

    //填表
    int ret = 0;
    for (int i = 1; i < n; i++){
        //状态转移方程 并存放到哈希表中
        dp[i] = hash[arr[i] - difference] + 1;
        hash[arr[i]] = dp[i];

        //更新返回结果
        ret = max(ret, dp[i]);
    }

    //返回值
    return ret;
}

//最长的斐波那契子序列的长度
//如果一个斐波那契子序列a,b,c如果只知道c的值，不一定能推出斐波那契子序列是哪个
//比如2，3，5或者1，4，5只知道5，并不能确定前两个值a,b是多少，但是如果能确定后两个值b,c，一定能确定前一个值a
int lenLongestFibSubseq(vector<int>& arr){
    int n = arr.size();

    //预处理 建立元素和下标的映射关系
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++){
        hash[arr[i]] = i;
    }

    // 状态表示 dp[i][j]表示以位置i和位置j的两个元素为结尾的所有子序列中，最长的斐波那契子序列长度
    // 其中下标i<下标j
    // 初始化 因为是两个下标的值所以序列长度最小为2
    vector<vector<int>> dp(n, vector<int>(n, 2));

    //填表
    int ret = 0;
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            //先找到前一个位置的下标k并判断是否顺序正确
            if (hash.count(arr[j] - arr[i]) != 0){
                int k = hash[arr[j] - arr[i]];
                if (k >= 0 && k < i){
                    dp[i][j] = dp[k][i] + 1;
                }
            }
            // 更新返回值
            ret = max(ret, dp[i][j]);
        }
    }

    //如果原序列中没有斐波那契子序列，ret的值还是为2，直接返回0
    return ret < 3 ? 0 : ret;
}



//1027.最长等差数列
int longestArithSeqLength(vector<int>& nums){
    int n = nums.size();

    //状态表示 dp[i][j]表示以i位置和j位置元素为结尾的所有子序列中，最长的等差数列长度
    //其中下标i<下标j
    //初始化 i位置和j位置元素组成的子序列就是一个等差数列，长度为2
    vector<vector<int>> dp(n, vector<int>(n, 2));

    //建议元素和下标的映射关系
    unordered_map<int, int> hash;
    hash[nums[0]] = 0;

    //填表
    int ret = 2;
    for (int i = 1; i < n; i++){
        //固定i位置的值，遍历j位置的值，
        //每当i位置的，所有j位置的值遍历完后，将i位置的值存放到哈希表中，防止重复元素出现导致下标映射错误
        for (int j = i + 1; j < n; j++){
            int a = nums[i] - (nums[j] - nums[i]);
            //判断前一个数是否存在
            if (hash.count(a) != 0){
                //找到前一个数的下标k
                int k = hash[a];
                //判断下标k是否顺序正确
                if (k >= 0 && k < i){
                    dp[i][j] = dp[k][i] + 1;
                }
            }

            //更新返回值
            ret = max(ret, dp[i][j]);
        }

        hash[nums[i]] = i;
    }

    //返回值 如果ret=2，说明原序列中不存在等差数列，直接返回0
    return ret;
}


//446.等差数列的划分2--子序列
int numberOfArithmeticSlices(vector<int>& nums){
    int n = nums.size();

    //预处理 建立元素和下标数组的映射关系
    unordered_map<long, vector<int>> hash;
    for (int i = 0; i < n; i++){
        //存在相同值但不同下标，所以下标存放到下标数组中
        hash[(long)nums[i]].push_back(i);
    }

    //状态表示 dp[i][j]表示以i位置和j位置元素为结尾的所有子序列中，是等差数列的个数
    //其中下标i<下标j
    //初始化 因为等差数列的最小长度为3，所以单独的两个元素不能组成等差数列，个数为0，状态表中初始值全部设置为0
    vector<vector<int>> dp(n, vector<int>(n));

    //填表
    int ret = 0;
    //固定i位置的值b，遍历所有以j位置的值c为结尾的等差子序列
    for (int i = 1; i < n; i++){
        for (int j = i + 1; j < n; j++){
            //找到前一个元素a,并找到对应的下标数组
            long a = (long)nums[i] - ((long)nums[j] - (long)nums[i]);
            if(hash.count(a)!=0){
                vector<int> index = hash[a];

                //遍历下标数组，找到所有的等差子序列
                for(auto k : index){
                    //判断下标是否顺序正确
                    if (k >= 0 && k < i){
                        //a,b,c同样也是等差数列，个数还要多加一
                        dp[i][j] += (dp[k][i] + 1);
                    }
                }

                //更新总的等差子序列个数
                ret += dp[i][j];
            }
        }
    }

    //返回值
    return ret;
}

int main(){

    return 0;
}